package leetcode

//https://leetcode.com/problems/reverse-nodes-in-k-group/
fun printNode(header: ListNode?) {
    var head = header
    while (head != null) {
        print("${head.`val`} \t")
        head = head?.next
    }
}

fun main(args: Array<String>) {
    val node = ListNode(1,null)
    printNode(reverseKGroup2(node, 5))
}

/**
 * 用数组保存，TLE
 */
fun reverseKGroup(head: ListNode?, k: Int): ListNode? {

    if (k == 1) return head
    //保存k个node的引用，方便后续逆序
    val nodes = ArrayList<ListNode?>(k)
    var resultHeader: ListNode? = null
    var header: ListNode? = head
    var chain: ListNode? = null
    var counter = 0
    do {
        nodes.clear()
        while (counter < k) {
            nodes.add(header)
            counter++
        }

        if (resultHeader == null)
            resultHeader = nodes[k - 1]

        //找到一组逆序
        if (nodes.size == k) {
            for (j in k - 1 downTo 1) {
                nodes[j]?.next = nodes[j - 1]
            }

            if (chain != null)
                chain.next = nodes[k - 1]
            chain = nodes[k - 1]
        }


    } while (nodes.size == k)

    return resultHeader
}

//////////////////////////////////提交的一组
fun reverseKGroup2(head: ListNode?, k: Int): ListNode? {
    if (k == 1) return head
    var resultHeader: ListNode? = null
    var chain: ListNode? = null
    var counter = 0

    var former: ListNode? = head
    var latter = former
    outer@ while (true) {

        inner@ while (counter < k - 1) {
            latter = latter?.next
            counter++

            if (latter == null) {
                chain?.next = former
                break@outer
            }
        }

        //保存下一组的第一个节点，不然后面的逆序操作会丢失链表信息
        val next = latter?.next

        if (resultHeader == null) resultHeader = latter
        //从former这个头节点开始反转
        var header = latter
        var tail = former
        header?.next = null //这里先置空,不然会链接到后面一组的第一个节点
        while (tail != header) {
            val tmp = tail?.next

            /**交换start**/
            val headerNext = header?.next
            header?.next = tail
            tail?.next = headerNext
            /**交换 end**/

            tail = tmp
        }
        if (chain != null)
            chain.next = header
        //保存尾部节点
        chain = former

        //准备寻找下一组
        counter = 0
        latter = next
        former = next
    }

    if (resultHeader == null){
        //可能k 大于链表长度，此时直接退出了while循环
        resultHeader = head
    }
    return resultHeader
}